/*
 * Heuristicas.c
 *
 *  Created on: Jun 2, 2009
 *      Author: gianpaolo
 */

#include "Heuristicas.h"

int ITER_LS = 0;


void greedy(int ** conexiones, int tamConex, int sInic[], int *sizeSol, int *valor) {
	int i;
	*sizeSol = 1;
	sInic[0] = 0;
	actualizar(sInic,*sizeSol,conexiones,tamConex,0);
	for (i = 1; i < tamConex; ++i) {
		if(conexiones[i][0] > 0) {
			verificarSol(sInic,sizeSol,i,tamConex);
			*valor += conexiones[i][0];
			actualizar(sInic,*sizeSol,conexiones,tamConex,i);
		}
	}
}

float getMiu(int** conexiones, int tamConex, int *cjtoAsignado) {
	int i,temp1,temp2,fila,adentro,afuera;
	int min = (int) MAXFLOAT, max = 0;

	for (i = 0; i < tamConex; ++i) {
		if (cjtoAsignado[i] == TRUE) continue;
		getPosition(&fila, &afuera, &adentro, i, tamConex);

		temp1 = conexiones[fila][afuera], temp2 = conexiones[fila][adentro];

		if(temp1 < temp2) {
			if(min > temp1) min = temp1; //minimo
			if(max < temp2) max = temp2; //maximo
		} else {
			if(min > temp2) min = temp2; //minimo
			if(max < temp1) max = temp1; //maximo
		}
	}

	return min + Random()*(max-min);
}

void makeRCL(int **conexiones, int tamConex, int *cjtoAsignado, int *candidatos, int *colaCandidatos) {
	int i,fila,adentro,afuera;
	float miu;

	*colaCandidatos = 0;
	miu = getMiu(conexiones, tamConex, cjtoAsignado); // Esta funcion debe tener
														// la semilla plantada
	for (i = 0; i < tamConex; ++i) {
		if(cjtoAsignado[i] == TRUE) continue;
		getPosition(&fila,&afuera,&adentro,i,tamConex);
		if(conexiones[fila][adentro] > miu) {
			candidatos[(*colaCandidatos)++] = i; continue;
		}
		if(conexiones[fila][afuera] > miu) {
			candidatos[(*colaCandidatos)++] = i;
		}
	}
}

void randomnized(int **conexiones, int tamConex, int sInic[], int *sizeSol, int *valor) {
	int i;
	double rdm ;
	*valor = 0;
	*sizeSol = 0;
	for (i = 0; i < tamConex; ++i) {
		rdm = Random()-Random();
		if(rdm > 0) {
			sInic[(*sizeSol)++] = i;
			*valor += conexiones[i][0];
			actualizar(sInic,*sizeSol,conexiones,tamConex,i);
		}
	}
}

void generarSol(int ** conexiones, int tamConex, int sInic[], int* sizeSol, int *valor, short int opcion) {

	switch (opcion) {
		case 1:
			return greedy(conexiones,tamConex,sInic,sizeSol, valor);
			break;
		case 2:
			return randomnized(conexiones,tamConex,sInic,sizeSol, valor);
			break;
		case 3:
			return greedyRandom(conexiones,tamConex,sInic,sizeSol,valor);
	}
}

void greedyRandom(int **conexiones, int tamConex, int sInic[], int *sizeSol, int *valor) {
	int cjtoAsignado[tamConex], i;
	int candidatos[tamConex], colaCandidatos = 0, index;

	//Inicializo la estructura de los conjuntos sin asignar
	for (i = 0; i < tamConex; ++i)
		cjtoAsignado[i] = FALSE;

	for (i = 0; i < tamConex*0.40; ++i) {
		makeRCL(conexiones, tamConex, cjtoAsignado, candidatos, &colaCandidatos);
		index = selectIndex(0,colaCandidatos);
		index = candidatos[index];
		cjtoAsignado[index] = TRUE;
		verificarSol(sInic,sizeSol,index,tamConex);
		*valor += conexiones[index][0];
		actualizar(sInic,*sizeSol,conexiones,tamConex,index);
		//printMatriz(conexiones,tamConex);
	}
}

void busquedaLocalPM(int **conexiones, int tamConex, int sAct[], int* colaAct,
		int *valor) {
	short int i, hayMejor;

	ITER_LS = 0;
	while (TRUE) {
		ITER_LS++;
		hayMejor = FALSE;
		for (i = 0; i < tamConex; ++i) {
			if (conexiones[i][0] > 0) {
				verificarSol(sAct, colaAct, i, NODOS);

				*valor += conexiones[i][0];
				hayMejor = TRUE;
				actualizar(sAct, *colaAct, conexiones, NODOS, i);

				break;
			}
		}
		if (!hayMejor)
			break;
	}
}

void busquedaLocalMM(int **conexiones, int tamConex, int sAct[], int *colaAct,
		int *valor) {
	short int i, hayMejor, mejorVec, valorMejorVec, aux;

	ITER_LS = 0;
	while (TRUE) {
		ITER_LS++;
		hayMejor = FALSE, mejorVec = -1, valorMejorVec = 0;
		for (i = 0; i < tamConex; ++i) {
			aux = conexiones[i][0];
			if (valorMejorVec < aux) {
				valorMejorVec = aux, mejorVec = i, hayMejor = TRUE;
			}
		}
		if (!hayMejor)
			break;
		else {
			verificarSol(sAct, colaAct, mejorVec, NODOS);

			*valor += valorMejorVec;
			actualizar(sAct, *colaAct, conexiones, NODOS, mejorVec);
		}
	}
}

void busquedaLocalSM(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor) {
	short int i, hayMejor;
	int candidatos[tamConex], colaCandidatos = 0, index;

	ITER_LS = 0;
	do {
		ITER_LS++;
		hayMejor = FALSE;
		colaCandidatos = 0;
		for (i = 0; i < tamConex; ++i) {
			if (conexiones[i][0] > 0) {
				candidatos[colaCandidatos++] = i;
			}
		}
		if (colaCandidatos > 0) {
			index = selectIndex(0,colaCandidatos-1);
			index = candidatos[index];
			verificarSol(sAct,colaAct,index,tamConex);
			*valor += conexiones[index][0];
			actualizar(sAct,*colaAct,conexiones,tamConex,index);
			hayMejor = TRUE;
		}
	} while(hayMejor);
}

void grasp(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor) {
	int i,mejorValor = *valor;
	int sPrima[tamConex], colaPrima=0;

	asignarArregloToArreglo(sAct, colaAct, sPrima, &colaPrima);
	for (i = 0; i < MAX_ITER; ++i) {
		//Se reinicia
		generarTabla(conexiones,tamConex);
		*valor = 0;
		*colaAct = 0;

		printf("iteracion %d\n",i+1);
		generarSol(conexiones, tamConex, sAct, colaAct, valor, 3);
		printf("\tValor Inicial: %d\t",*valor);

		busquedaLocalPM(conexiones,tamConex,sAct,colaAct,valor);
		printf("\tValor Final: %d\t",*valor);
		printf("Numero de iteraciones %d\n", ITER_LS);
		if(*valor > mejorValor) mejorValor = *valor;
		//else {
			//asignarArregloToArreglo(sPrima, &colaPrima, sAct, colaAct);
			//*valor = mejorValor;
		/*}*/
	}
	*valor = mejorValor;
}

void lis(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor) {
	int i,mejorValor = *valor;
	int sPrima[tamConex], colaPrima=0;

	asignarArregloToArreglo(sAct, colaAct, sPrima, &colaPrima);
	for (i = 0; i < MAX_ITER; ++i) {

		//Perturba la mejor solucion encontrada
		printf("iteracion %d\n",i+1);
		generarSol(conexiones, tamConex, sAct, colaAct, valor, 3);
		printf("\tValor Inicial: %d\t",*valor);

		busquedaLocalPM(conexiones,tamConex,sAct,colaAct,valor);
		printf("\tValor Final: %d\t",*valor);
		printf("Numero de iteraciones %d\n", ITER_LS);
		if(*valor > mejorValor) mejorValor = *valor;
		else {
			asignarArregloToArreglo(sPrima, &colaPrima, sAct, colaAct);
			*valor = mejorValor;
		}
	}
	*valor = mejorValor;
}

void tabu(int **conexiones, int tamConex, int sAct[], int *colaAct,
		int *valor) {
	short int i, x, hayOpcion, mejorVec, valorMejorVec, aux, mejorSol, 
	contadorTabu, maxTabu, listaTabu[TABU_MEM], noesta, iterTabu;
	
	iterTabu = 0;
	maxTabu = 1;
	for(contadorTabu = 0; contadorTabu < TABU_MEM; contadorTabu++){
		listaTabu[contadorTabu] = -1;
	}
	contadorTabu = 0;
	generarTabla(conexiones,tamConex);
	generarSol(conexiones,tamConex,sAct,colaAct,valor,2); //Creo una solucion random
	mejorSol = *valor;
	
	while (TRUE) {
		printf("iter %d \n", iterTabu);
		hayOpcion = FALSE, mejorVec = -1, valorMejorVec = -1000000, noesta = TRUE;
		for (i = 0; i < tamConex; ++i) {
			aux = conexiones[i][0];
			if (valorMejorVec < aux) {
				//me aseguro que no sea un valor tabu.
				for (x = 0; x < TABU_MEM; x++){
					if (i == listaTabu[x]){
						noesta = FALSE;
					}
				}
				if(noesta){
					valorMejorVec = aux, mejorVec = i, hayOpcion = TRUE;
				}
			}
		}
		if (!hayOpcion)
			break;
		if (iterTabu > 10000)
			break;
		else {
			if(maxTabu < TABU_MEM) maxTabu++;
			listaTabu[contadorTabu] = mejorVec;
			contadorTabu++;
			if(contadorTabu >= TABU_MEM) contadorTabu = 0;
			iterTabu++;
			
			verificarSol(sAct, colaAct, mejorVec, NODOS);

			*valor += valorMejorVec;
			actualizar(sAct, *colaAct, conexiones, NODOS, mejorVec);
		}
	}
}
